package tianhao.luo.algorithm;

import java.util.Arrays;

/**
 * 克鲁斯卡尔算法
 *
 * @author: tianhao.luo@hand-china.com 2021/7/3  10:29
 */
public class KruskalAlgorithm {

    private Graph graph;

    public KruskalAlgorithm(Graph graph) {
        this.graph = graph;
    }

    public EData[] kruskal(){
        // 表示最后结果数组的索引
        int index = 0;
        //  用于保存"已有最小生成树"中的每个顶点在最小生成树中的终点
        int[] ends = new int[graph.edgeNum];
        // 创建结果数组,保存最后的最小生成树
        EData[] results = new EData[graph.edgeNum];
        // 获取图中的所有边的集合
        EData[] edges = graph.getEdges();
        // 按照边的权值大小进行排序
        graph.sortEdges(edges);
        // 遍历edges,将边添加到最小生成树中,并判断准备加入的边是否构成回路了;如果没有就,加入ends,否则不能加入
        for (int i = 0; i < graph.edgeNum; i++) {
            // 获取第i条边的起点
            int p1 = graph.getPosition(edges[i].start);
            // 第i条边的终点
            int p2 = graph.getPosition(edges[i].end);
            // 获取p1顶点在已有的最小生成树中终点是哪个
            int m = graph.getEnd(ends,p1);
            // 获取p2在已有最小生成树中的终点
            int n = graph.getEnd(ends,p2);
            // 是否构成回路
            if (m != n){ // 不构成回路
                // 设置m在已有最小生成树中的终点
                ends[m] = n;
                // 有一条边加入
                results[index++] = edges[i];
            }
        }
        // 打印
        System.out.println("最小生成树的边:");
        for (int i = 0; i < index; i++) {
            System.out.println(results[i]);
        }
        return results;
    }

    static class Graph {
        /**
         * 边的个数
         */
        private int edgeNum;
        /**
         * 顶点数组
         */
        private char[] vertexs;
        /**
         * 邻接矩阵
         */
        private int[][] matrix;
        /**
         * 两个顶点间不能联通
         */
        public static final int INF = -1;

        public Graph(char[] vertexs, int[][] matrix) {
            // 初始化顶点数和边的个数
            this.vertexs = vertexs;
            this.matrix = matrix;

            // 统计边
            for (int i = 0; i < vertexs.length; i++) {
                // 自己不与自己相连
                for (int j = i + 1; j < vertexs.length; j++) {
                    if (matrix[i][j] != INF) {
                        edgeNum++;
                    }
                }
            }
        }


        public void print() {
            System.out.println("邻接矩阵为: \n");
            for (int i = 0; i < vertexs.length; i++) {
                for (int j = 0; j < vertexs.length; j++) {
                    System.out.printf("%4d \t", matrix[i][j]);
                }
                System.out.println();
            }
        }

        /**
         * 对边进行按权值从小到大排序
         *
         * @param eData 边集合
         */
        private void sortEdges(EData[] eData) {
            for (int i = 0; i < eData.length - 1; i++) {
                for (int j = 0; j < eData.length - 1 - i; j++) {
                    if (eData[j].weight > eData[j + 1].weight) {
                        EData temp = eData[j];
                        eData[j] = eData[j + 1];
                        eData[j + 1] = temp;
                    }
                }
            }
        }

        /**
         * @param ch 顶点,比如 A B等
         * @return 下标, 找不到就返回-1
         */
        private int getPosition(char ch) {
            for (int i = 0; i < vertexs.length; i++) {
                if (vertexs[i] == ch) {
                    return i;
                }
            }
            // 找不到,返回-1
            return -1;
        }

        /**
         * 功能:获取图中的边,放到EData[] 数组中,后面我们需要遍历该数组
         * 通过matrix邻接矩阵获取到
         * 存放
         *
         * @return 图中所有边
         */
        private EData[] getEdges() {
            int index = 0;
            EData[] edges = new EData[edgeNum];

            for (int i = 0; i < matrix.length; i++) {
                // 统计边时,无需和自己连接
                for (int j = i + 1; j < matrix[i].length; j++) {
                    if (matrix[i][j] != INF) {
                        edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
                    }
                }
            }
            return edges;
        }

        /**
         * 获取下标为i的顶点的终点,用于后面判断两个顶点的终点是否相同
         *
         * @param ends 数组记录了各个顶点对应的终点是哪个;ends数组是遍历过程中,逐步生成的
         * @param i    表示传入的顶点,对应的下标
         * @return 返回的就是下标为i的这个顶点对应的终点的下标
         */
        private int getEnd(int[] ends, int i) {
            while (ends[i] != 0) {
                i = ends[i];
            }
            return i;
        }
    }

    /**
     * 边
     */
    static class EData {
        /**
         * 一条边起点
         */
        char start;
        /**
         * 一条边终点
         */
        char end;
        /**
         * 权值
         */
        int weight;

        public EData(char start, char end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer("EData{");
            sb.append("<").append(start);
            sb.append(",").append(end);
            sb.append(">=").append(weight);
            sb.append('}');
            return sb.toString();
        }
    }
}
